package com.fm.base.struct;

import java.util.Collection;
import java.util.Iterator;
import java.util.Set;

public class BasicHashSet<E> extends HashTable<E> implements Set<E> {
	protected static final float DEFAULT_LOAD_FACTOR = 0.75F;
	protected static final float DEFAULT_EXPAND_FACTOR = 1F;

	private static class BasicHashNode<E> implements HashNode<E> {
		private E element;
		private BasicHashNode<E> next;

		private BasicHashNode(E element) {
			this.element = element;
		}

		@Override
		public E getElement() {
			return element;
		}

		@Override
		public HashNode<E> getNext() {
			return next;
		}

		@Override
		public void setNext(HashNode<E> next) {
			this.next = (BasicHashNode<E>) next;
		}
	}

	public BasicHashSet() {
		this(1, DEFAULT_LOAD_FACTOR, DEFAULT_EXPAND_FACTOR);
	}

	public BasicHashSet(int initialCapacity) {
		this(initialCapacity, DEFAULT_LOAD_FACTOR);
	}

	public BasicHashSet(int initialCapacity, float loadFactor) {
		this(initialCapacity, loadFactor, DEFAULT_EXPAND_FACTOR);
	}

	@SuppressWarnings({"unchecked"})
	public BasicHashSet(int initialCapacity, float loadFactor, float expandFactor) {
		if (initialCapacity < 0) {
			throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
		} else if (initialCapacity == 0) {
			initialCapacity = 1;
		}
		if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
			throw new IllegalArgumentException("Illegal loadFactor: " + loadFactor);
		} else {
			this.loadFactor = loadFactor;
		}
		if (expandFactor <= 0 || Float.isNaN(expandFactor)) {
			throw new IllegalArgumentException("Illegal expandFactor: " + expandFactor);
		} else {
			this.expandFactor = expandFactor;
		}
		table = (BasicHashNode<E>[]) new BasicHashNode[initialCapacity];
		threshold = (int) Math.min(initialCapacity * loadFactor, Integer.MAX_VALUE);
	}

	@Override
	protected int hash(E element) {
		return element == null ? 0 : element.hashCode();
	}

	@Override
	@SuppressWarnings("unchecked")
	protected void reHash() {
		if (table.length >= Integer.MAX_VALUE) {
			return;
		}
		int newCapacity = (int) Math.ceil(table.length * (1 + expandFactor));
		if (newCapacity <= 0) {
			newCapacity = Integer.MAX_VALUE;
			threshold = Integer.MAX_VALUE;
		} else {
			threshold = (int) (newCapacity * loadFactor);
		}
		BasicHashNode<E>[] newTable = (BasicHashNode<E>[]) new BasicHashNode[newCapacity];
		for (HashNode<E> row : table) {
			BasicHashNode<E> node = (BasicHashNode<E>) row;
			while (node != null) {
				int i = render(hash(node.element), newTable.length);
				BasicHashNode<E> next = node.next;
				node.next = newTable[i];
				newTable[i] = node;
				node = next;
			}
		}
		table = newTable;
	}

	@Override
	@SuppressWarnings("unchecked")
	public boolean contains(Object e) {
		HashNode<E> node = getNode((E) e);
		return node != null;
	}

	@Override
	@SuppressWarnings("unchecked")
	public E[] toArray() {
		E[] array = (E[]) new Object[size];
		int i = 0;
		for (E e : this) {
			array[i++] = e;
		}
		return array;
	}

	@Override
	public <T> T[] toArray(T[] a) {
		throw new UnsupportedOperationException();
	}

	@Override
	public boolean add(E e) {
		int hash = hash(e);
		int index;
		BasicHashNode<E> node = (BasicHashNode<E>) table[index = render(hash, table.length)];
		if (node == null) {
			table[index] = new BasicHashNode<>(e);
		} else {
			while (true) {
				if (hash == hash(node.element)) {
					E cur = node.element;
					if (cur == null) {
						if (e == null) {
							return false;
						}
					} else {
						if (cur.equals(e)) {
							return false;
						}
					}
				}
				if (node.next != null) {
					node = node.next;
				} else {
					break;
				}
			}
			node.next = new BasicHashNode<>(e);
		}
		if (++size > threshold) {
			reHash();
		}
		return true;
	}

	public BasicHashSet<E> append(E e) {
		add(e);
		return this;
	}

	@Override
	public boolean containsAll(Collection<?> c) {
		for (Object e : c) {
			if (!contains(e)) {
				return false;
			}
		}
		return true;
	}

	@Override
	public boolean addAll(Collection<? extends E> c) {
		boolean modified = false;
		for (E e : c) {
			if (add(e)) {
				modified = true;
			}
		}
		return modified;
	}

	@Override
	public boolean removeAll(Collection<?> c) {
		boolean modified = false;
		for (Object e : c) {
			if (remove(e)) {
				modified = true;
			}
		}
		return modified;
	}

	@Override
	public boolean retainAll(Collection<?> c) {
		boolean modified = false;
		Iterator<E> it = iterator();
		while (it.hasNext()) {
			if (!c.contains(it.next())) {
				it.remove();
				modified = true;
			}
		}
		return modified;
	}

	@Override
	@SuppressWarnings("unchecked")
	public boolean remove(Object e) {
		return removeNode((E) e) != null;
	}

	@Override
	public void clear() {
		for (int i = 0; i < table.length;) {
			table[i++] = null;
		}
		size = 0;
	}

	@Override
	public Iterator<E> iterator() {
		return new Iterator<E>() {
			boolean needLoop = true;
			int index = -1;
			BasicHashNode<E> pre = null;
			BasicHashNode<E> cur = null;

			@Override
			public boolean hasNext() {
				if (needLoop) {
					if (cur != null && cur.next != null) {
						pre = cur;
						cur = cur.next;
						needLoop = false;
						return true;
					} else {
						pre = null;
						for (index++; index < table.length; index++) {
							if (table[index] != null) {
								cur = (BasicHashNode<E>) table[index];
								needLoop = false;
								return true;
							}
						}
					}
				} else {
					return cur != null;
				}
				return false;
			}

			@Override
			public E next() {
				needLoop = true;
				return cur.element;
			}

			@Override
			public void remove() {
				if (cur != null) {
					if (pre != null) {
						pre.next = cur.next;
					} else {
						table[index] = cur.next;
					}
				}
			}
		};
	}

	@Override
	public String toString() {
		StringBuilder builder = new StringBuilder();
		builder.append("[");
		Iterator<E> iterator = iterator();
		while (iterator.hasNext()) {
			builder.append(iterator.next());
			if (iterator.hasNext()) {
				builder.append(",");
			}
		}
		builder.append("]");
		return builder.toString();
	}
}
